\chapter{Resultados de Álgebra Linear e Análise convexa}
\begin{description}
	\item [2.24] Qual a solução geral do seguinte sistema?
	\[
		\begin{array}{l}
			x_1 + 2x_2 + x_3 = 3 \\
			-x_1 + 5x_2 + x_3 = 6
		\end{array}
	\]
	
	\begin{solution}
	Isolando $x_1$ na primeira equação temos
	\[
		x_1 = 3 - 2x_2 - x3
	\]
	e substituindo na segunda equação temos
	\[
		\begin{array}{l}
			-3 + 2x_2 + x_3 +5x_2 + x_3 = 6 \\
			7x_2 + 2x_3 = 9 \\
			x_3 = \frac{9 - 7x_2}{2}
		\end{array}
	\]
	de modo que a solução geral é $(\frac{-3 + 3\alpha}{2}, \alpha, \frac{9 - 7\alpha}{2})$.
	\end{solution}
	
	\item [2.25] Encontre todas as soluções básicas do sistema
	\[
		\begin{array}{l}
			-x_1 + x_2 + x_3 + x_4 - 2x_5 = 4 \\
			x_1 - 2x_2 + x_4 - x_5 = 3
		\end{array}
	\]
	
	\begin{solution}
	Existem $\binom{5}{2} = 10$ soluções básicas. Vamos apresentar uma ficando a cargo do leitor as demais.
	Para $x_3 = x_4 = x_5 = 0$ temos o seguinte sistema
	\[
		\begin{array}{l}
			-x_1 + x_2 = 4 \\
			x_1 - 2x_2 = 3
		\end{array}
	\]
	que tem como solução $x_1 = -11, x_2 = -7$ de modo que uma das soluções básicas desejadas é $(-11,-7,0,0,0)$.
	\end{solution}
	
	\item [2.26] Determine a solução do sistema
	\[
		\begin{array}{l}
			x_1 + 3x_2 + x_3 - x_4 = 1 \\
			5x_2 - 6x_3 + x_4 = 0 \\
			x_1 - 2x_2 + 4x_3 = 1
		\end{array}
	\]
	
	\begin{solution}
	Aplicando a Eliminação de Gauss temos:
	\[
		\begin{array}{l}
			x_1 + 3x_2 + x_3 - x_4 = 1 \\
			5x_2 - 6x_3 + x_4 = 0 \\
			5x_2 - 3x_3 -x_4 = 0
		\end{array}
	\]
	\[
		\begin{array}{l}
			x_1 + 3x_2 + x_3 - x_4 = 1 \\
			5x_2 - 6x_3 + x_4 = 0 \\
			3x_3 - 2x_4 = 0
		\end{array}
	\]
	de modo que a solução é $(\frac{15 - 32\alpha}{15}, \frac{3\alpha}{5}, \frac{2\alpha}{3}, \alpha)$.
	\end{solution}
	
	\item [2.30] Considere o conjunto $\{ (x_1,x_2): -x_1 + x_2 \leq 2, x_1 + 2x_2 \leq 8, x1 \geq 0, x_2 \geq 0 \}$. Qual a menor distância do ponto $(4,4)$ ao conjunto? Qual o ponto do conjunto mais próximo de $(4,4)$?
	
	\begin{solution}
	Na Figura \ref{fig:Ex2.30} encontramos a ilustração do conjunto.
	\begin{figure}[!h]
		\centering
		\begin{tikzpicture}[scale=0.3,domain=-0.2:9.2]
			\fill[color=gray!20] (0,0) -- (0,2) -- (1.3,3.3) -- (8,0) -- (0,0);
			
			\draw[very thin,color=gray] (-0.1,-2.1) grid (8.9,11.9);
			
			\draw[->] (-0.2,0) -- (9.2,0) node[right] {$x_1$};
			\draw[->] (0,-2.2) -- (0,12.2) node[above] {$x_2$};
			
			\clip (-0.2,-2.8) rectangle (19.2,12.2);
			
			\draw[color=blue] plot (\x,2+\x) node[right] {$-x_1 + x_2 \leq 2$};
			\draw[color=red] plot (\x,0.5*8 - 0.5*\x) node[right] {$x_1 + 2x_2 \leq 8$};
			
			\fill[color = black] (4,4) circle (0.2) node[right] {$(4,4)$};
		\end{tikzpicture}
		\caption{Figura do exercicio 2.30.} \label{fig:Ex2.30}
	\end{figure}
	
	Pela figura notamos que o menor ponto do conjunto e $(4,4)$ é a solução do sistema
	\[
		\begin{array}{l}
			x_1 + 2x_2 = 8 \\
			x_1 - x_2 = 0
		\end{array}	
	\]
	isso é, o ponto $(\frac{8}{3}, \frac{8}{3})$ e a distância é $\frac{\sqrt{32}}{3}$.
	\end{solution}
	
	\item [2.32] Seja $a_1 = (1,0)$, $a_2 = (2,3)$, $a_3 = (-1,4)$, $a_4 = (5,3)$ e $a_5 = (-4,3)$. Ilustre geometricamente a coleção de todos os pontos que são combinação convexa destes cinco pontos.
	
	\begin{solution}
	A Figura \ref{fig:Ex2.32} representa o desejado.
	\begin{figure}[!h]
		\centering
		\begin{tikzpicture}[scale=0.4,domain=-0.2:9.2]
			\filldraw[fill=gray!20, draw=black] (1,0) -- (5,3) -- (-1,4) -- (-4,3) -- (1,0);
			
			\draw[very thin,color=gray] (-6.1,-1.1) grid (6.9,5.9);
			
			\draw[->] (-6.2,0) -- (7.2,0) node[right] {$x_1$};
			\draw[->] (0,-1.2) -- (0,6.2) node[above] {$x_2$};
			
			\clip (-6.2,-2.8) rectangle (7.2,7.2);
			
			\fill[color = black] (1,0) circle (0.2) node[right] {$(1,0)$};
			\fill[color = black] (2,3) circle (0.2) node[below left] {$(2,3)$};
			\fill[color = black] (-1,4) circle (0.2) node[above right] {$(-1,4)$};
			\fill[color = black] (5,3) circle (0.2) node[right] {$(5,3)$};
			\fill[color = black] (-4,3) circle (0.2) node[above] {$(-4,3)$};
		\end{tikzpicture}
		\caption{Figura do exercicio 2.32.} \label{fig:Ex2.32}
	\end{figure}
	\end{solution}
	
	\item [2.40] Encontre todos os pontos extremos do seguinte conjunto poliedrico: $X = \{ (x_1, x_2, x_3): x_1 + x_2 + x_3 \leq 1, -x_1 + x_2 \leq 4, x_1, x_2, x_3 \geq 0 \}$.
	
	\begin{solution}
	Sabemos que o conjunto $X$ possui no máximo $\binom{5}{3} = 10$ pontos extremos. Iremos testar um possível ponto extremo e os demais ficam a cargo do leitor.
	
	Um possível ponto extremo é a solução do sistema
	\[
		\begin{array}{l}
			x_1 + x_2 + x_3 = 1 \\
			-x_1 + 2x_2 = 4 \\
			x_3 = 0
		\end{array}
	\]
	Aplicando a Eliminação de Gauss temos que o ponto $(-\frac{2}{3}, \frac{5}{3}, 0)$ é solução do sistema. Como $x_1 \geq 0$ em $X$ temos que $(-\frac{2}{3}, \frac{5}{3}, 0)$ não é ponto extremo de $X$.
	\end{solution}
	
	\item [2.41] Encontre os pontos extremos da região definida pelas seguintes inequações
	\[
		\begin{array}{l}
			x_1 + x_2 + x_3 \leq 5 \\
			-x_1 + x_2 + 2x_3 \leq 6 \\
			x_1, x_2, x_3 \geq 0
		\end{array}
	\]
	
	\begin{solution}
	Iremos introduzir variáveis de folga ao sistema de modo que obtemos
	\[
		\begin{array}{l}
			x_1 + x_2 + x_3 + x_4 = 5 \\
			-x_1 + x_2 + 2x_3 + x_5 = 6 \\
			x_1, x_2, x_3, x_4, x_5 \geq 0
		\end{array}
	\]
	e considerar as soluções básicas (temos $\binom{5}{2} = 10$ soluções básicas). Iremos encontrar uma solução básica e verificar se ela é factível sendo que as demais ficam a cargo do leitor.
	
	Consideremos $x_3 = x_4 = x_5 = 0$, temos então o sistema
	\[
		\begin{array}{l}
			x_1 + x_2 = 5 \\
			-x_1 + x_2 = 6
		\end{array}
	\]
	cuja solução é $x_1 = -\frac{1}{2}$, $x_2 = \frac{11}{2}$. Como $x_1 \leq 0$ temos que essa solução básica não é factível e portanto não corresponde a um ponto extremo.
	\end{solution}
	
	\item [2.45] O sistema
	\[
		\begin{array}{l}
			-x_1 + x_2 = 4 \\
			x_1 + x_2 + x_3 \leq 6 \\
			x_3 \geq 1 \\
			x_1, x_2, x_3 \geq 0
		\end{array}
	\]
	possui alguma direção?
	
	\begin{solution}
	Vamos substituir $x_3$ por $x_4 + 1$ e introduzir variáveis de folga no sistema de modo que obtemos
	\[
		\begin{array}{l}
			-x_1 + x_2 = 4 \\
			x_1 + x_2 + x_4 + x_5 = 5 \\
			x_1, x_2, x_4, x_5 \geq 0
		\end{array}
	\]
	Será que existe $\mathbf{d} > \mathbf{0}$ tal que
	\[
		\left[ \begin{array}{cccc}
			-1 & 1 & 0 & 0 \\
			1 & 1 & 1 & 1
		\end{array} \right] \mathbf{d} = \mathbf{0}
	\]
	É fácil verificar que não existe tal $\mathbf{d}$ de modo que o sistema não possui direção.
	\end{solution}
	
	\item [2.50] Seja $X = \{(x_1, x_2): x_1 - x_2 \leq 3, 2x_1 + x_2 \leq 4, x_1 \geq -3 \}$. Encontre todos os pontos extremos de $X$ e represente o ponto $(0,1)$ como uma combinação convexa dos pontos extremos.
	
	\begin{solution}
	A Figura \ref{fig:Ex2.50} dá uma ajuda em encontrar uma combinação convexa dos pontos extremos para representar o ponto $(0,1)$.
	\begin{figure}[!h]
	\centering
		\begin{tikzpicture}[scale=0.4,domain=-3.2:4.2]
			\fill[color=gray!20] (-3,-6) -- (2.35,-0.65) -- (-3,10);
			
			\draw[very thin,color=gray] (-4.1,-7.1) grid (4.9,10.9);
			
			\draw[->] (-4.2,0) -- (5.2,0) node[right] {$x_1$};
			\draw[->] (0,-7.2) -- (0,11.2) node[above] {$x_2$};
			
			\clip (-4.2,-7.2) rectangle (10.2,14.2);

			\draw[color=blue] plot (\x,-3+\x) node[right] {$x_1 - x_2 \leq 3$};
			\draw[color=red] plot (\x,4-2*\x) node[right] {$2x_1 + x_2 \leq 4$};
			\draw[color=green] plot (-3,3*\x) node[above right] {$x_1 \geq -3$};
			
			\fill[color = black] (0,1) circle (0.2) node[right] {$(0,1)$};
		\end{tikzpicture}
		\caption{Figura do exercicio 2.50.} \label{fig:Ex2.50}
	\end{figure}
	\end{solution}
	
	\item [2.53] Seja $\mathbf{A} = \left[ \begin{array}{ll}
		1 & 1 \\
		0 & 2 \\
		-1 & 4
	\end{array} \right]$ e $\mathbf{c} = (1,4)$. Qual dos sistemas abaixo possue solução?
	\[
		\begin{array}{l}
			\mbox{Sistema 1: } \mathbf{A}\mathbf{x} \leq \mathbf{0}, \mathbf{c}^T \mathbf{x} > 0 \\
			\mbox{Sistema 2: } \mathbf{A}^T\mathbf{w} = \mathbf{c}, \mathbf{w} > 0 \\
		\end{array}
	\]
	
	\begin{solution}
	A Figura \ref{fig:Ex2.53} mostra que o Sistema 2 possui solução.
	\begin{figure}[!h]
		\centering
		\begin{tikzpicture}[scale=1,domain=-3.2:4.2]
			\fill[color=gray!20] (0,0) -- (3,3) -- (3,6) -- (-1*1.5,4*1.5);
			
			\draw[very thin,color=gray] (-2.1,-1.1) grid (2.9,5.9);
			
			\draw[->] (-2.2,0) -- (3.2,0) node[right] {$x_1$};
			\draw[->] (0,-1.2) -- (0,6.2) node[above] {$x_2$};

			\draw[->] (0,0) -- (1,1) node[above right] {$(1,1)$};
			\draw[->] (0,0) -- (0,2) node[above] {$(0,2)$};
			\draw[->] (0,0) -- (-1,4) node[above right] {$(-1,4)$};

			\draw[->] (0,0) -- (1,4) node[above right] {$\mathbf{c} = (1,4)$};
		\end{tikzpicture}
		\caption{Região factível do exercicio 2.53.} \label{fig:Ex2.53}
	\end{figure}
	
	Pelo Teorema de Farkas, como o Sistema 2 possue solução o Sistema 1 não possue.
	\end{solution}
\end{description}
